using System.Collections.Generic;
using UnityEngine;

public class Dijkstra
{
    public class NodeInfo
    {
        public long GridId;
        public int Value;
        public long PreGrid;
    }

    Dictionary<long, NodeInfo> path = new Dictionary<long, NodeInfo>();
    HashSet<long> isAlready = new HashSet<long>();

    public Dijkstra() { }

    public List<long> PathFind(Grid begin, Grid end, Dictionary<long, GameObject> info)
    {
        if (begin.Id == end.Id) return new List<long>();

        path.Clear();
        isAlready.Clear();
        path.Add(begin.Id, new NodeInfo { GridId = begin.Id, Value = 0, PreGrid = -1 });
        isAlready.Add(begin.Id);

        var candidate = new List<Grid>();

        var node = begin;
        while (true)
        {
            GetCandidates(candidate, node, info);

            if (candidate.Count == 0)
            {
                break;
            }

            var nextId = candidate[0].Id;
            if (nextId != node.Id)
            {
                if (path.TryGetValue(node.Id, out var ni))
                {
                    if (path.TryGetValue(nextId, out var nextInfo))
                    {
                        if (nextInfo.Value < ni.Value + 1)
                        {
                            nextInfo.Value = ni.Value + 1;
                            nextInfo.PreGrid = node.Id;
                            if (nextInfo.PreGrid == nextInfo.GridId)
                            {
                                Debug.LogError("PreGrid Equal to Self Id");
                                break;
                            }
                        }
                    }
                }
            }
            else
            {
                Debug.LogWarning($"Same Node Id: {nextId}");
            }
            node = candidate[0];
            candidate.RemoveAt(0);
        }

        if (path.Count > 0)
        {
            path.TryGetValue(end.Id, out var inode);
            var result = new List<long>();
            while (inode != null)
            {
                if (result.Count > 1000)
                {
                    break;
                }
                result.Add(inode.GridId);
                var pre = inode.PreGrid;
                if (!path.TryGetValue(pre, out inode))
                {
                    Debug.LogWarning($"Can't find node {pre}, result: {result.Count}");
                    break;
                }
            }
            isAlready.Clear();
            path.Clear();
            return result;
        }

        return null;
    }

    private void GetCandidates(List<Grid> candidates, Grid node, Dictionary<long, GameObject> info)
    {
        // up
        var upId = (node.Row + 1) * 10000 + node.Col;
        if (info.TryGetValue(upId, out var upperObj) && !isAlready.Contains(upId))
        {
            candidates.Add(upperObj.GetComponent<Grid>());
            isAlready.Add(upId);
            if (!path.ContainsKey(upId))
                path.Add(upId, new NodeInfo { GridId = upId, PreGrid = node.Id, Value = int.MaxValue });
            MarkCandidate(upperObj);
        }

        //down
        var downId = (node.Row - 1) * 10000 + node.Col;
        if (info.TryGetValue(downId, out var downObj) && !isAlready.Contains(downId))
        {
            isAlready.Add(downId);
            candidates.Add(downObj.GetComponent<Grid>());
            if (!path.ContainsKey(downId))
                path.Add(downId, new NodeInfo { GridId = downId, PreGrid = node.Id, Value = int.MaxValue });
            MarkCandidate(downObj);
        }
        // left
        var leftId = node.Row * 10000 + node.Col - 1;
        if (info.TryGetValue(leftId, out var leftObj) && !isAlready.Contains(leftId))
        {
            isAlready.Add(leftId);
            candidates.Add(leftObj.GetComponent<Grid>());
            if (!path.ContainsKey(leftId))
                path.Add(leftId, new NodeInfo { GridId = leftId, PreGrid = node.Id, Value = int.MaxValue });
            MarkCandidate(leftObj);
        }
        //right
        var rightId = node.Row * 10000 + node.Col + 1;
        if (info.TryGetValue(rightId, out var rightObj) && !isAlready.Contains(rightId))
        {
            isAlready.Add(rightId);
            if (!path.ContainsKey(rightId))
                path.Add(rightId, new NodeInfo { GridId = rightId, PreGrid = node.Id, Value = int.MaxValue });
            candidates.Add(rightObj.GetComponent<Grid>());
            MarkCandidate(rightObj);
        }
    }

    private void MarkCandidate(GameObject obj)
    {
        obj.GetComponent<MeshRenderer>().material.color = Color.cyan;
    }
}
